package algorithm

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// TailTraverse 后续遍历
func TailTraverse(t *TreeNode) {
	if t == nil {
		return
	}

	TailTraverse(t.Left)
	TailTraverse(t.Right)
	fmt.Println(t.Val)
}

// RecoverSearchTree 搜索二叉树 给 后序遍历的数组  重归成搜索树 返回头节点  左-右-根
// 字节面试题;
func RecoverSearchTree(nums []int) *TreeNode {
	return recovery(nums, 0, len(nums)-1)
}

// 时间复杂度 棒状结构 n-1 + n-2 + .. + 1; O(NN); 找左右子树 是通过遍历的;
// 其实可以二分的; 时间复杂度O(nlgN)
func recovery(nums []int, l, r int) *TreeNode {
	if l > r {
		return nil
	}

	t := &TreeNode{nums[r], nil, nil}
	if l == r {
		return t
	}

	var M int

	// 夹逼 我们要找左半边右边界这个索引;
	for l <= r {
		m := l + (r-l)>>1
		if nums[r] < nums[m] {
			r = m - 1
		} else {
			M = m
			l = m + 1
		}
	}

	// m 左子树的右边界;
	t.Left = recovery(nums, l, M)
	t.Right = recovery(nums, M+1, r-1)
	return t
}

// LeftRightBound 找左子树的右边界
func LeftRightBound(nums []int) int {
	var (
		size   = len(nums)
		target = nums[size-1]
		l      = 0
		r      = size - 2
		m      int
		M      int
	)

	for l <= r {
		m = l + (r-l)>>1
		// [m, len-1] 这个区间的数都是大于target 不是我们找的数 我们要找小于target的最大的数的索引
		if nums[m] < target {
			M = m
			l = m + 1
		} else {
			r = m - 1
		}
	}

	return M
}
